package listbyorder.access001_100.test60;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/2 11:21
 */
public class Solution2 {

    // 300 栈 （自己想到的方法，练coding）
    public String getPermutation(int n, int k) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            nums.add(i + 1);
        }
        return getAns(nums, n, k);
    }

    private String getAns(List<Integer> nums, int n, int k) {
        if (n == 1) {
            return "" + nums.get(0);
        }
        // 计算当前n-1对应的元素个数
        int perGroupNum = factorial(n - 1);
        int groupNum = (k - 1) / perGroupNum;
        int num = nums.get(groupNum);
        nums.remove(groupNum);   // 选中了一次之后，后面就不可以选了，所以这里要清0
        k = k % perGroupNum;
        k = k == 0 ? perGroupNum : k;
        return num + getAns(nums, n - 1, k);   // 一个数一个数的向下进行递归
    }

    private int factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }
}
